import collections


class Solution(object):
    def shortestAlternatingPaths(self, n, redEdges, blueEdges):
        red = collections.defaultdict(set)
        blue = collections.defaultdict(set)
        for u, v in redEdges:
            red[u].add(v)
        for u, v in blueEdges:
            blue[u].add(v)
        red_out = [-1] * n
        blue_out = [-1] * n
        red_out[0] = 0
        blue_out[0] = 0
        red_now = {0}
        blue_now = {0}
        while red_now or blue_now:
            next_red = set()
            next_blue = set()
            for u in red_now:
                for v in blue[u]:
                    if blue_out[v] == -1 or red_out[u] + 1 < blue_out[v]:
                        blue_out[v] = red_out[u] + 1
                        next_blue.add(v)
            for u in blue_now:
                for v in red[u]:
                    if red_out[v] == -1 or blue_out[u] + 1 < red_out[v]:
                        red_out[v] = blue_out[u] + 1
                        next_red.add(v)
            red_now = next_red
            blue_now = next_blue
        ans = [0] * n
        for i in range(n):
            if red_out[i] == -1:
                if blue_out[i] == -1:
                    ans[i] = -1
                else:
                    ans[i] = blue_out[i]
            else:
                if blue_out[i] == -1:
                    ans[i] = red_out[i]
                else:
                    ans[i] = min(red_out[i], blue_out[i])
        return ans


data = Solution()
n = 3
red_edges = [[0, 1]]
blue_edges = [[2, 1]]
print(data.shortestAlternatingPaths(n, red_edges, blue_edges))
